package com.data.structure.linkedlist;

import java.util.Stack;

/**
 * 单链表
 *
 * @author wangjie
 * @version V1.0
 * @date 2019/12/24
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {

        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero4);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        System.out.println("原来链表的情况~~");
        singleLinkedList.list();
        System.out.println("测试逆序打印单链表, 没有改变链表的结构~~");
        reversePrint(singleLinkedList.getHead());
    }

    /**
     * 逆序打印单链表
     * @param head
     */
    public static void reversePrint(HeroNode head) {
        if (head.next != null) {
            Stack<HeroNode> stack = new Stack();

            for(HeroNode cur = head.next; cur != null; cur = cur.next) {
                stack.push(cur);
            }

            while(stack.size() > 0) {
                System.out.println(stack.pop());
            }

        }
    }

    /**
     * 单链表逆序
     * @param head
     */
    public static void reversetList(HeroNode head) {
        if (head.next != null && head.next.next != null) {
            HeroNode cur = head.next;
            HeroNode next = null;

            HeroNode reverseHead;
            for(reverseHead = new HeroNode(0, "", ""); cur != null; cur = next) {
                next = cur.next;
                cur.next = reverseHead.next;
                reverseHead.next = cur;
            }

            head.next = reverseHead.next;
        }
    }

    /**
     * 找到单链表倒数第N个节点
     * @param head
     * @param index
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        if (head.next == null) {
            return null;
        } else {
            int size = getLength(head);
            if (index > 0 && index <= size) {
                HeroNode cur = head.next;

                for(int i = 0; i < size - index; ++i) {
                    cur = cur.next;
                }

                return cur;
            } else {
                return null;
            }
        }
    }

    /**
     * 单链表长度
     * @param head
     * @return
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        } else {
            int length = 0;

            for(HeroNode cur = head.next; cur != null; cur = cur.next) {
                ++length;
            }

            return length;
        }
    }
}

/**
 * 单链表
 */
class SingleLinkedList {
    private HeroNode head = new HeroNode(0, "", "");

    SingleLinkedList() {
    }

    public HeroNode getHead() {
        return this.head;
    }

    public void add(HeroNode heroNode) {
        HeroNode temp;
        for(temp = this.head; temp.next != null; temp = temp.next) {
        }

        temp.next = heroNode;
    }

    public void addByOrder(HeroNode heroNode) {
        HeroNode temp = this.head;

        boolean flag;
        for(flag = false; temp.next != null && temp.next.no <= heroNode.no; temp = temp.next) {
            if (temp.next.no == heroNode.no) {
                flag = true;
                break;
            }
        }

        if (flag) {
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    public void update(HeroNode newHeroNode) {
        if (this.head.next == null) {
            System.out.println("链表为空~");
        } else {
            HeroNode temp = this.head.next;

            boolean flag;
            for(flag = false; temp != null; temp = temp.next) {
                if (temp.no == newHeroNode.no) {
                    flag = true;
                    break;
                }
            }

            if (flag) {
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
            } else {
                System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
            }

        }
    }

    public void del(int no) {
        HeroNode temp = this.head;

        boolean flag;
        for(flag = false; temp.next != null; temp = temp.next) {
            if (temp.next.no == no) {
                flag = true;
                break;
            }
        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }

    }

    public void list() {
        if (this.head.next == null) {
            System.out.println("链表为空");
        } else {
            for(HeroNode temp = this.head.next; temp != null; temp = temp.next) {
                System.out.println(temp);
            }

        }
    }

}

/**
 * 链表节点
 */
class HeroNode {

    public int no;
    public String name;
    public String nickname;
    public HeroNode next;
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }

}